package com.heima.leetcode.algorithm.greedy;

import java.util.Arrays;

/**
 * 零钱兑换I 322
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/30 9:32
 */
public class ChangeOne {
    /*
         硬币面值：5 2 1     总金额：18
         选：5    剩：13
         选：5    剩：8
         选：5    剩：3
         选：2    剩：1
         选：1    剩：0
         最小硬币数：5
         贪心思想就是只看当下，只选择当前的最理想的情况，但是有可能会解决错误

         硬币面值：15 10 1   总金额：21
         选：15    剩：6
         选：1     剩：5
         选：1     剩：4
         选：1     剩：3
         选：1     剩：2
         选：1     剩：1
         选：1     剩：0
         最小硬币数：7 ，但是很显然 10 + 10 + 1 = 21，最小硬币数应该是3，解答错误

         硬币面值：15 10    总金额：20
         选：15    剩：5
         无解，但实际上是 10 + 10 = 20，最小硬币数应该是2，解答错误
     */
    public int coinChange(int amount, int[] coins) {
        int count = 0;
        coins = Arrays.stream(coins)
                .boxed()
                .sorted((o1,o2)->Integer.compare(o2,o1))
                .mapToInt(Integer::intValue)
                .toArray();
        for (int coin : coins) {
            while (amount >= coin){
                amount -= coin;
                count++;
            }
            if (amount == 0){
                break;
            }
        }
        if (amount != 0){
            return -1;
        }
        return count;
    }
}
